Cycle index

In mathematics, and in particular in the field of combinatorics, cycle indices are used in combinatorial enumeration when symmetries are to be taken into account. This is particularly important in species theory.

Each permutation π of a finite set of objects partitions that set into cycles; the cycle index monomial of π is a monomial in variables a1, a2, … that describes the type of this partition (the cycle type of π): the exponent of ai is the number of cycles of π of size i. The cycle index polynomial of a permutation group is the average of the cycle index monomials of its elements. The terms cycle index and cycle indicator are also used, both for the cycle index monomial of a permutation and for the cycle index polynomial of a group.

Knowing the cycle index polynomial of a permutation group, one can enumerate equivalence classes of objects that arise when the group acts on a set of slots being filled with objects described by a generating function. This is the most common application and it uses the Pólya enumeration theorem.

Contents

Definition

The cycle index of a permutation group G is the average of

a_1^{j_1(g)} a_2^{j_2(g)} a_3^{j_3(g)} \cdots

over all permutations g of the group, where jk(g) is the number of cycles of length k in the disjoint cycle decomposition of g.

More formally, let G be a permutation group of order m and degree n. Every permutation g in G has a unique decomposition into disjoint cycles, say c1 c2 c3 ... Let the length of a cycle c be denoted by |c|.

Now let jk(g) be the number of cycles of g of length k, where

0 \le j_k(g) \le \lfloor n/k \rfloor \mbox{ and }
\sum_{k=1}^n k \, j_k(g) \; = n.

We associate to g the monomial

 \prod_{c\in g} a_{|c|} = \prod_{k=1}^n a_k^{j_k(g)}

in the variables a1, a2, ... an.

Then the cycle index Z(G) of G is given by

 Z(G) = \frac{1}{|G|} \sum_{g\in G} \prod_{k=1}^n a_k^{j_k(g)}.

The question of what the cycle structure of a random permutation looks like is an important question in the analysis of algorithms. An overview of the most important results may be found at random permutation statistics.

Examples

Basic examples of disjoint cycle decompositions may be found here.

The cyclic group C3 = {e,(1 2 3),(1 3 2)} consists of the identity and two 3-cycles. Thus its cycle index is

Z(C_3) = \frac{1}{3} \left( a_1^3 %2B 2 a_3 \right).

The symmetric group S3 has the elements

S_3 = \{e,(2 3),(1 2),(1 2 3),(1 3 2),(1 3)\}

and its cycle index is

Z(S_3) = \frac{1}{6} 
\left( a_1^3 %2B 3 a_1 a_2 %2B 2 a_3 \right).

The cyclic group C6 contains the six permutations

[1 2 3 4 5 6] = (1)(2)(3)(4)(5)(6)
[2 3 4 5 6 1] = (1 2 3 4 5 6)
[3 4 5 6 1 2] = (1 3 5)(2 4 6)
[4 5 6 1 2 3] = (1 4)(2 5)(3 6)
[5 6 1 2 3 4] = (1 5 3)(2 6 4)
[6 1 2 3 4 5] = (1 6 5 4 3 2).

and its cycle index is

Z(C_6) = \frac{1}{6} 
\left( a_1^6 %2B a_2^3 %2B 2 a_3^2 %2B 2 a_6 \right).

Case study: edge permutation group of graphs on three vertices

Consider graphs on three vertices. Every permutation in the group S3 of vertex permutations induces an edge permutation and we want to compute the cycle index of the latter group. These are the permutations:

No vertices are permuted, and no edges; the contribution is a_1^3.\,

These fix one edge (the one not incident on the vertex) and exchange the remaining two; the contribution is 3 a_1 a_2.\,

These create a cycle of three edges; the contribution is 2 a_3.\,

The cycle index of the group G of edge permutations induced by vertex permutations from S3 is

 Z(G) = \frac{1}{6} \left(a_1^3 %2B 3 a_1 a_2 %2B 2 a_3 \right)

It happens that K3 is its own dual and hence the edge permutation group induced by the vertex permutation group is the same as the vertex permutation group, namely S3 and the cycle index is Z(S3). This is not the case for graphs on more than three vertices, where the vertex permutation group has degree n and the edge permutation group has degree n(n − 1)/2. For n > 3 we have n(n − 1)/2 > n. We will see an example in the next section.

Case study: edge permutation group of graphs on four vertices

We compute the cycle index of the edge permutation group for graphs on four vertices. The process is entirely analogous to the three-vertex case. These are the vertex permutations and the edge permutations that they induce:

This permutation maps all vertices (and hence, edges) to themselves and the contribution is a_1^6.\,

These permutations preserve the edge that connects the two vertices as well as the edge that connects the two vertices not exchanged. The remaining edges form two two-cycles and the contribution is 6 a_1^2 a_2^2.\,

These permutations create two three-cycles of edges, one containing those not incident on the vertex, and another one containing those incident on the vertex; the contribution is 8 a_3^2.\,

These permutations preserve the two edges that connect the two pairs. The remaining edges form two two-cycles and the contribution is 3 a_1^2 a_2^2.\,

These permutations create a four-cycle of edges (those that lie on the cycle) and exchange the remaining two edges; the contribution is 6 a_2 a_4.\,

Note that we may visualize the types of permutations as symmetries of a regular tetrahedron. This yields the following description of the permutation types.

We have computed the cycle index of the edge permuation group G of graphs on four vertices and it is


Z(G) = \frac{1}{24}
\left(
a_1^6 %2B 9 a_1^2 a_2^2 %2B 8 a_3^2 %2B 6 a_2 a_4
\right).

Case study: face permutations of a cube

Consider an ordinary cube in three-space and its automorphisms under rotations, which form a group, call it C. It permutes the six faces of the cube. (We could also consider edge permutations or vertex permutations.) There are twenty-four automorphisms. We will classify them all and compute the cycle index of C.

There is one such permutation and its contribution is a_1^6.

We rotate about the axis passing through the centers of the face and the face opposing it. This will fix the face and the face opposing it and create a four-cycle of the faces parallel to the axis of rotation. The contribution is 6 a_1^2 a_4.

We rotate about the same axis as in the previous case, but now there is no four cycle of the faces parallel to the axis, but rather two two-cycles. The contribution is 3 a_1^2 a_2^2.

This time we rotate about the axis passing through two opposite vertices (the endpoints of a main diagonal). This creates two three-cycles of faces (the faces incident on the same vertex form a cycle). The contribution is 8 a_3^2.

These edge rotations rotate about the axis that passes through the midpoints of opposite edges not incident on the same face and parallel to each other and exchanges the two faces that are incident on the first edge, the two faces incident on the second edge, and the two faces that share two vertices but no edge with the two edges, i.e. there are three two-cycles and the contribution is 6 a_2^3.

The conclusion is that the cycle index of the group C is

Z(C) = \frac{1}{24}
\left(
a_1^6 %2B 6 a_1^2 a_4 %2B 3 a_1^2 a_2^2 %2B 8 a_3^2 %2B 6 a_2^3
\right)
.

Cycle indices of some groups

Identity group En

This group contains one permutation that fixes every element.

 Z(E_n) = a_1^n

Cyclic group Cn

Cyclic group is the group of rotations of n elements round a circle.

 Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}

This formula is easily verified for powers of primes n=p^v, where we use the fact that the cyclic group is isomorphic to the group generated by g= \exp 2 \pi i / n with multiplication being the group operation. It is thus readily apparent that the order of g^k is LCM(k, n)/k or n/GCD(n, k). The possible values of the order are 1, p, p^2, p^3, \ldots, p^v according to whether GCD(n, k) = p^v, p^{v-1}, p^{v-2}, \ldots, 1. But the number of solutions from the interval [1, n] to GCD(n, k) = p^{v-w} is one when w=0 and p^w - p^{w-1} otherwise, so that the number of elements of each order is 1, p-1, p^2-p, \ldots, p^v-p^{v-1}, giving

 Z(C_n) = \frac{1}{p^v} \sum_{w=0}^v \varphi(p^w) a_{p^w}^{p^{v-w}}

which is the formula from above (where we have taken into account that a permutation of order p^w splits into p^{v-w} cycles, each of which is obtained by a single application of g).

Dihedral group Dn

Dihedral group is like the cyclic group, but also includes reflections.

 Z(D_n) = \frac{1}{2} Z(C_n) %2B
\begin{cases}
\frac{1}{2} a_1 a_2^{(n-1)/2}, & n \mbox{ odd, } \\ 
\frac{1}{4}
\left( a_1^2 a_2^{(n-2)/2} %2B a_2^{n/2} \right), & n \mbox{ even.}
\end{cases}

The alternating group An

The alternating group includes all even n! permutations of n elements.

 Z(A_n) = 
\sum_{j_1%2B2 j_2 %2B 3 j_3 %2B \cdots %2B k j_k = n}
\frac{1 %2B (-1)^{j_2%2Bj_4%2B\cdots}}{\prod_{k=1}^n k^{j_k} j_k!} \prod_{k=1}^n a_k^{j_k}

The symmetric group Sn

The cycle index of the symmetric group Sn is given by the formula:

 Z(S_n) = \sum_{j_1%2B2 j_2 %2B 3 j_3 %2B \cdots %2B k j_k = n} \frac{1}{\prod_{k=1}^n k^{j_k} j_k!} \prod_{k=1}^n a_k^{j_k}

that can be also stated in terms of complete Bell polynomials:

 Z(S_n) = \frac{B_n(0!\,a_1, 1!\,a_2, \dots, (n-1)!\,a_n)}{n!}.

This formula is obtained by counting how many times a given permutation shape can occur. There are three steps: first partition the set of n labels into subsets, where there are j_k subsets of size k. Every such subset generates k!/k cycles of length k. But we do not distinguish between cycles of the same size, i.e. they are permuted by S_{j_k}. This yields


\frac{n!}{\prod_{k=1}^n (k!)^{j_k}} 
\prod_{k=1}^n \left( \frac{k!}{k} \right)^{j_k}
\prod_{k=1}^n \frac{1}{j_k!}
=
\frac{n!}{\prod_{k=1}^n k^{j_k} j_k!}.

There is a useful recursive formula for the cycle index of the symmetric group. Set Z(S_0) = 1 and consider the size l of the cycle that contains n, where \begin{matrix}1 \le l \le n.\end{matrix} There are \begin{matrix}{n-1 \choose l-1}\end{matrix} ways to choose the remaining l-1 elements of the cycle and every such choice generates \begin{matrix}\frac{l!}{l}\end{matrix} different cycles.

This yields the recurrence

 Z(S_n) = \frac{1}{n!} \sum_{g\in S_n} \prod_{k=1}^n a_k^{j_k(g)}
= 
\frac{1}{n!} 
\sum_{l=1}^n {n-1 \choose l-1} \;  \frac{l!}{l} \;  a_l \; (n-l)! \; Z(S_{n-l})

or


Z(S_n) =  \frac{1}{n} \sum_{l=1}^n a_l \; Z(S_{n-l}).

External links